Ngày 20 tháng 9 năm 1955, linh mục Nguyễn Văn Bình được Toà Thánh bổ nhiệm làm giám mục Hiệu tòa Agnusiensi, Đại diện Tông Tòa Hạt Đại diện Tông tòa Cần Thơ.[25] Lễ tấn phong cho vị giám mục Tân cử được tổ chức tại nhà thờ Đức Bà Sài Gòn ngày 30 tháng 11 cùng năm, với phần nghi thức truyền chức chính yếu cử hành bởi Chủ phong là Giám mục Phêrô Máctinô Ngô Đình Thục, Đại diện Tông tòa Địa phận Vĩnh Long và hai giám mục Phụ phong là Giám mục Jean Cassaigne, nguyên Đại diện Tông Tòa Địa phận Sài Gòn và Tađêô Lê Hữu Từ, Đại diện Tông Tòa Địa phận Phát Diệm.[26] Cùng được tấn phong trong dịp này có Tân Đại diện Tông Tòa Địa phận Sài Gòn Simon Hòa Nguyễn Văn Hiền.[27]

Nguyễn Văn Bình chính thức nhận Địa phận Cần Thơ vào ngày 20 tháng 12 năm 1955, khi linh mục Tổng Đại diện Antôn Nguyễn Văn Thiện chào đón tân giám mục tại cầu Bắc Cần Thơ. Ngày hôm sau, giám mục Bình cử hành lễ đầu tiên tại núi Đức Mẹ Lộ Đức, nơi ông đã thực hiện nghi thức thánh hiến (làm phép) vào ngày hôm trước. Tham dự lễ này có các giám mục người Việt đầu tiên và đang hiện diện tại miền Nam: Phêrô Máctinô Ngô Đình Thục, Tađêô Lê Hữu Từ, Phêrô Maria Phạm Ngọc Chi, Giuse Trương Cao Đại và Simon Hòa Nguyễn Văn Hiền.[4]

Khi được chia tách khỏi Địa phận Nam Vang, Địa phận Cần Thơ không có bất kỳ cơ sở chính yếu nào: không tòa Giám mục, không nhà thờ Chính tòa, không Chủng viện, tu viện và không có ngân sách tài chính. Sau khi nhậm chức cai quản địa phận, Nguyễn Văn Bình triệu tập các linh mục trong địa phận, bàn bạc, xem xét và xây dựng chương trình phát triển địa phận. Sau khi thảo luận xong, giám mục Bình tập trung nguồn nhân lực thuộc địa phận, tìm kiếm sự hỗ trợ,... Ông ưu tiên xây dựng các cơ sở tôn giáo và đào tạo nhân sự.[4] Ông cũng chú trọng đến việc gầy dựng sự thiện cảm bằng cách đến thăm các gia đình tại các vùng xa xôi. Việc này thu được kết quả: ngoài Cần Thơ, một số vùng khác cũng có thiện cảm với giám mục Bình.[20]

Nguyễn Văn Bình chọn Nhà thờ Cầu Xéo làm Nhà thờ Chính Địa phận. Linh mục Antôn Nguyễn Văn Thiện, chính xứ Cầu Xéo được bổ nhiệm làm linh mục Tổng Đại diện Địa phận. Sau khi chọn nhà thờ chính, giám mục Bình triển khai xây dựng Tiểu chủng viện Á Thánh Quý. Ngày 1 tháng 4 năm 1956, bắt đầu khởi công xây tạm bằng cây, mái lá, sàn lót gạch Tàu ở địa điểm cạnh bên nhà thờ Sóc Trăng. Sau khi xây dựng tạm, Nguyễn Văn Bình đưa các chủng sinh thuộc các khối Đệ Thất đến Đệ Tam, tuyển thêm cho các lớp Đệ Nhất và Đệ Nhị. Ngày 15 tháng 9 năm 1956, chính thức khai giảng năm học mới với số chủng sinh là 138. Chỉ một tháng sau đó, ngày 16 tháng 10, chủng viện được khánh thành với tên gọi Á Thánh Quý (lấy theo tên Chân phước Phêrô Đoàn Công Quý). Giám mục Bình cũng đến địa phận Sài Gòn, mời gọi các linh mục giáo sư về giảng dạy tại Địa phận Cần Thơ. Hai năm đầu tiếp quản Địa phận Cần Thơ, Nguyễn Văn Bình sống tại nhà xứ của nhà thờ Chính tòa Cần Thơ. Năm 1957, ông mua đất và nhà Vallery, nay trên đường Nguyễn Trãi, Cần Thơ và cho sửa sang lại để sử dụng. Cuối tháng 11 năm 1958, ông cho làm phép và khánh thành Tòa giám mục.[4]

Giám mục Nguyễn Văn Bình cho thiết lập dòng nữ Tu Mến Thánh Giá nhằm mục đích hỗ trợ giáo sĩ truyền giáo trong địa phận. Linh mục Nicôla nhượng lại ngôi trường cũ trên mảnh đất 14.000 m2 cho địa phận. Chính linh mục này được giám mục Bình bổ nhiệm làm Bề Trên tiên khởi của dòng nữ Mến Thánh Giá và nhờ 4 nữ tu Dòng Con Đức Bà Rousseykeo (Nam Vang) hỗ trợ đào tạo các nữ tu. Tháng 10 năm 1957, dòng đã lần đầu khai giảng, số lượng 32 thiếu nữ. Trong thời kỳ ban đầu, Nguyễn Văn Bình cũng gửi một số ít nữ tu đến học tại Dòng Mến Thánh Giá Chợ Quán, trong đó có nữ tu Magarita Sanh, em ruột của ông.[4]

Nhận thấy thiếu nơi nghỉ ngơi cho các linh mục công tác tại Sài Gòn, Nguyễn Văn Bình cho xây dựng trụ sở Địa phận Cần Thơ tại Sài Gòn. Trụ sở có địa chỉ 2A Lương Hữu Khánh, Phạm Ngũ Lão, Sài Gòn. Tháng 10 năm 1957, ngôi nhà này chính thức hoàn thành, một phần nhờ sự hỗ trợ của giám mục Simon Hòa Nguyễn Văn Hiền, linh mục chính xứ Chợ Đũi và linh mục chính xứ Cầu Kho trong việc tìm kiếm địa điểm.[28] Giám mục Nguyễn Văn Bình cũng quan tâm đến sức khỏe các linh mục, khuyến khích họ mỗi năm nghỉ 1 tháng, chọn địa điểm phù hợp dự định xây nhà nghỉ mát linh mục ở Hòn Chông. Sau khi tách giáo phận Long Xuyên năm 1960, Hòn Chông thuộc tân giáo phận còn giám mục Bình trở thành Tổng giám mục Sài Gòn, dự định này bất thành. Nhằm mục đích sản xuất lương thực cho chủng viện và nhà dòng, Nguyễn Văn Bình quyết định mua 5 mẫu đất gần cầu Bình Thủy để tiến hành trồng trọt, chăn nuôi. Giám mục Bình cũng tiến hành mua một chiếc xe vận tải hạng nhẹ nhằm mục đích chở vật liệu xây dựng và mua sắm hàng hóa.[4][29]

Với mục đích phát hành các ấn phẩm Công giáo và sách giáo khoa, văn học, Nguyễn Văn Bình tiến hành mua lại một nhà in lớn, đặt tên là Cần Thơ Án Quán, bổ nhiệm linh mục Anphongsô Nguyễn Thiên Tứ làm giám đốc. Địa phận cho phát hành bán nguyệt san Thực Hành với số lượng 2.300 bản cho mỗi số nhằm mục đích liên kết giáo dân và giáo sĩ, khích lệ phong trào Công giáo Tiến hành.[4] Tờ báo Công giáo của Địa phận được giám mục Bình cho thành lập ngay trong năm đầu tiên ông quản lý địa phận, năm 1955.[30]

Trước năm 1954, nhiều nhà thờ trên địa bàn Địa phận bị hư hại. Nguyễn Văn Bình cho sửa chữa nhiều nơi, trong đó có bảy nhà thờ phải xây lại hoàn toàn. Ngoài ra, ông cũng cho thiết lập thêm nhiều giáo họ. Thời kỳ này, có nhiều giáo dân di cư từ Miền Bắc đến địa phận Cần Thơ, giám mục Bình sắp xếp cho định cư tại Cái Sắn, Định Hải và Phú Quốc. Tết năm 1957, ông tiếp nhận số lượng Việt kiều từ Campuchia hồi hương và cho họ định cư gần Cà Mau.[4] Trong năm 1958, ông bàn giao cựu chủng viện Cù Lao Giêng cho các nam tu sĩ dòng Phan Sinh quản lý.[31]

Ngoài việc xây dựng các công trình tôn giáo, Nguyễn Văn Bình còn quan tâm đến việc đào tạo giáo sĩ: Có thời kỳ số linh mục là 45 cử hành mục vụ cho 83.000 giáo dân. Nhận thấy khó khăn này, giám mục Địa phận đào tạo giáo dân trong Ban Quới chức nhằm hỗ trợ các linh mục, đồng thời khích lệ Công giáo Tiến hành. Ngoài ra, giám mục Bình thành lập Hội cựu tu sĩ Địa phận Cần Thơ và nhờ họ trợ giúp các linh mục làm các công tác mục vụ: dạy giáo lý, sinh hoạt các giới,... Nhóm này giao cho linh mục Nguyễn Thiên Tứ làm Giám đốc, tổ chức hội nghị mỗi ba tháng. Tiếp đến, Nguyễn Văn Bình cho khai mở các trường tư thục Công giáo, dần dần khoảng gần 10 trường Công giáo xuất hiện, dạy học theo chương trình chính phủ với học viên không phân biệt tôn giáo. Để tìm kiếm giáo viên, giám mục Bình lập đoàn giáo viên với các thanh niên chưa lập gia đình và có ước muốn tham gia để tuyển chọn, huấn luyện về phương pháp dạy học và giáo lý và điều động họ đi dạy tại các trường Công giáo vùng quê, có huấn luyện bổ sung. Tháng 11 năm 1956, Tòa Thánh phê chuẩn Hiến chương Công giáo Tiến hành. Giám mục Nguyễn Văn Bình khích lệ phong trào này dưới quyền linh mục Tổng đại diện Antôn Nguyễn Văn Thiện. Ngoài tờ báo Thực Hành để khích lệ, ông còn cho lập hai hội: Hùng Tâm Dũng Chí và Đạo Binh Đức Mẹ.[4] Trong thời kỳ này, linh mục Philípphê Nguyễn Kim Điền cùng một số tu sĩ dòng Tiểu Đệ đến sinh sống tại Bình Thủy, Cần Thơ. Giám mục Nguyễn Văn Bình đã hỗ trợ nhóm này bằng việc phụ công kéo lá.[20]

Tính đến cuối tháng 11 năm 1959, Nguyễn Văn Bình đạt được các kết quả khả quan trog các vấn đề xây dựng các cơ sở xã hội của mình: Trường trung học, tiểu học, mẫu giáo Công giáo có đều ở các tỉnh trong Giáo phận dạy số nam sinh là trên 12.000 và số nữ sinh trên 10.000, phần lớn là người Công giáo. Số linh mục tăng từ 52 linh mục địa phương năm 1955 lên 142 và số giáo dân tăng lên 150.201. Số Quới chức và các Thầy giảng là 1.427 người.[4] Trong thời kỳ này, ngoài xây dựng các cơ sở tôn giáo, đào tạo nhân sự, Nguyễn Văn Bình còn quan tâm đến việc cải thiện đời sống cho giáo dân tại các giáo điểm mới. Ông thường xuyên đi đến các tỉnh khác nhau để trao Bí tích Thêm Sức hoặc chiếu phim nhằm cải thiện đời sống. Trên các chuyến ghe đến các vùng khó khăn, ông an ủi và khuyến khích giáo dân sống đạo tốt.[19]

Trong làn sóng di cư vào miền Nam, giám mục Bình có công sắp đặt và bình thường hóa cho hơn nửa triệu người Công giáo di cư. Ông cũng quan tâm hạn chế những đố kị giữa người Công giáo hai miền, quyết định pha trộn tạo nên các họ đạo, dòng tu, hội đoàn và trường tư thục Công giáo gồm thành phần cả Công giáo miền Nam và miền Bắc.[32]